﻿// 247 亚特兰蒂斯 代码3.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*

https://www.acwing.com/problem/content/249/

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。

您的朋友 Bill 必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。

输入格式
输入包含多组测试用例。

对于每组测试用例，第一行包含整数 n，表示总的地图数量。

接下来 n 行，描绘了每张地图，每行包含四个数字 x1,y1,x2,y2
（不一定是整数），(x1,y1)和 (x2,y2)分别是地图的左上角位置和右下角位置。

注意，坐标轴 x 轴从上向下延伸，y 轴从左向右延伸。

当输入用例 n=0 时，表示输入终止，该用例无需处理。

输出格式
每组测试用例输出两行。

第一行输出 Test case #k，其中 k 是测试用例的编号，从 1 开始。

第二行输出 Total explored area: a，其中 a 是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次）
，精确到小数点后两位数。

在每个测试用例后输出一个空行。

数据范围
1≤n≤10000,
0≤x1<x2≤100000,
0≤y1<y2≤100000

注意，本题 n 的范围上限加强至 10000。

输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00

样例解释
样例所示地图覆盖区域如下图所示，两个矩形区域所覆盖的总面积，即为样例的解。

无标题.png
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>


using namespace std;

const int N = 100010;
struct segment {
	//存储线段信息
	double x, y1, y2;
	int d; //-1 +1 赋值
	bool operator<(const segment& t) const {
		return x < t.x;
	}
}seg[N]; //N个点构成N-1个线段？？

//线段树每个节点 保存的为线段，0号点为y[0]到y[1]，依此类推
struct node {
	int l, r;
	int cnt;	//记录区间覆盖情况
	double len;	//记录区间长度
}tr[N*4];
vector<double> ys;	//离散化的容器
int n;

int find(double y) {
	//需要返回vector中第一个 >= y 的数的下标。
	return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}


void pushup(int u) {
	//例如 假设tr[1].l = 0 tr[1].r=1;
	// y[0]为 ys[0]到ys[1]的距离，y[1]为ys[1]到ys[2]的距离
	//tr[1].len等于y[0]到y[1]的距离
	//y[1] = ys[tr[1].r+1] = ys[2] y[0] = ys[tr[1].l]= ys[0]
	if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
	//表示整个区间都被覆盖，该段长度就为右端点 + 1后在ys中的值 - 左端点在ys中的值
	// 如果tr[u].cnt等于0其实有两种情况:
	// 1. 完全覆盖. 这种情况由modify的第一个if进入. 
	//    这时下面其实等价于把"由完整的l, r段贡献给len的部分清除掉", 
	//    而留下其他可能存在的子区间段对len的贡献
	// 2. 不完全覆盖, 这种情况由modify的else最后一行进入. 
	//    表示区间并不是完全被覆盖，可能有部分被覆盖,所以要通过儿子的信息来更新
	else if (tr[u].l != tr[u].r) {
		tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
	}
	else tr[u].len = 0;	//表示为叶子节点且该线段没被覆盖完全，为无用线段 长度为0
}


void modify(int u, int l, int r, int d) //表示从线段树中l到r的出现次数+d
{
	if (tr[u].l >= l && tr[u].r <= r)	//区间完全覆盖
	{
		tr[u].cnt += d;
		pushup(u);
	}
	else {
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (l <= mid) modify(u << 1, l, r, d);
		if (r > mid) modify(u << 1 | 1, l, r, d);
		pushup(u);
	}
}

void build(int u, int l, int r) {
	tr[u] = { l,r,0,0 };
	if (l != r) {
		int mid = l + r >> 1;
		build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
	}
}


int main()
{
	int T = 1;
	while (cin >> n, n) {
		ys.clear();
		int j = 0;
		for (int i = 0; i < n; i++) {
			double x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			seg[j++] = { x1,y1,y2,1 };
			seg[j++] = { x2,y1,y2,-1 };
			ys.push_back(y1), ys.push_back(y2);
		}
		sort(seg, seg + j);

		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end());

		//例子：假设现在有三个不同的y轴点,分为两个线段
		//y[0] ~ y[1],y[1] ~ y[2];
		//此时ys.size()为3,ys.size() - 2 为 1;
		//此时为 build(1, 0, 1);
		//有两个点0 和 1,线段树中0号点为y[0] ~ y[1],1号点为y[1] ~ y[2];
		build(1, 0, ys.size() - 2);

		double res = 0;
		for (int i = 0; i < j; i++) {
			//根节点的长度即为此时有效线段长度，再乘以x轴长度即为面积
			if (i)res += tr[1].len * (seg[i].x - seg[i - 1].x);
			//处理一下该线段的信息 是加上该线段还是消去
			 //例子：假设进行modify(1，find(10),find(15) - 1,1);
			//      假设find(10) = 0,find(15) = 1;
			//      此时为modify(1, 0, 0, 1);
			//      表示线段树中0号点出现次数加1；
			//      而线段树中0号点刚好为线段(10 ~ 15);
			//      这就是为什么要进行find(seg[i].y2) - 1 的这个-1操作
			modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].d);
		}

		printf("Test case #%d\n",T++);
		printf("Total explored area: %.2lf\n\n",res);
	}

	return 0;
}

